package main

import (
	"fmt"
	"sort"
	"strconv"
)

// https://leetcode-cn.com/problems/next-greater-element-iii/

func main() {
	nums := 2147483647
	res := nextGreaterElement(nums)
	fmt.Println(res)
}

const INT_MAX = int(^uint32(0) >> 1)

// 需求
//	1) 给定一个32位的整数
//	2) 调整整数的各个数字，
//  3) 获取最小的的整数，此整数必须大于给定的整数，此整数必须小于INT_MAX,
//  4) 这个题条件不清晰，如果一个数字既可以组装成大于INT_MAX, 又能组装成小于INT_MAX, 是不是需要判断，　官方解题思路是比对最终结果，并没有分条件判断
// 思路：从后向前排序, 查找，　求最小数
func nextGreaterElement(n int) int {
	// 转[]byte数组
	numsSlice := []byte(strconv.Itoa(n))
	tmpNums := make([]byte, 0)
	done := false
	for i := len(numsSlice) - 1; i >= 0; i-- {
		num := numsSlice[i]
		tmpNums = append([]byte{num}, tmpNums...)

		// 最少大于等于２做判断
		if len(tmpNums) < 2 {
			continue
		}

		// 如果第一位大于第二位　跳过
		if tmpNums[0] >= tmpNums[1] {
			continue
		}

		// 排序查找尾数组
		if !done {
			minIndex := 1
			min := tmpNums[minIndex]

			// 找到大于第一位的最小数，和第一位互换位置
			for k := minIndex; k < len(tmpNums); k++ {
				if tmpNums[k] > tmpNums[0] && tmpNums[k] < min {
					min = tmpNums[k]
					minIndex = k
				}
			}

			tmpNums[minIndex] = tmpNums[0]
			tmpNums[0] = min

			// 除第一位外　从小到大排序
			tailNum := tmpNums[1:]
			// 后Ｎ位排序
			sort.Slice(tailNum, func(i, j int) bool {
				return tailNum[i] < tailNum[j]
			})

			// 完成拼装
			tmpNums = append([]byte{tmpNums[0]}, tailNum...)

			done = true
		}
	}

	findNum, _ := strconv.Atoi(string(tmpNums))
	if findNum <= n || findNum >= INT_MAX {
		return -1
	}

	return findNum
}

/**
解题思路
1). 假定 i := 3456753
2). 1. 必须大于 i ，2. 所有的数字组合中最小

１. 从后向前递归求最小数
	53,   　不变
	753,　　不变
	6753, 　在753中找到比比６大的最小数，调换位置，　然后对后三位从小到大排序　变成7356
2. 结果 3457356
*/
